import { isPrimeNum, bitCount } from '../../helper'

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
export var countPrimeSetBits = function (left, right) {
  let count = 0
  for (let i = left; i <= right; i++) {
    if (isPrimeNum(bitCount(i))) {
      count++
    }
  }
  return count
}

/**
 * 官方题解
right ≤ 10^6 < 2^20
 ，因此二进制中 11 的个数不会超过 1919，而不超过 1919 的质数只有

2, 3, 5, 7, 11, 13, 17, 19
我们可以用一个二进制数 {mask}=665772=10100010100010101100_{2}

来存储这些质数，其中 mask 二进制的从低到高的第 i 位为 1 表示 i 是质数，为 0 表示 i 不是质数。
设整数 x 的二进制中 1 的个数为 c，若 mask 按位与 2^c 不为 0，则说明 c 是一个质数。

 * @param {number} left
 * @param {number} right
 * @return {number}
 */
export var countPrimeSetBits2 = function (left, right) {
  let ans = 0
  for (let x = left; x <= right; ++x) {
    if (((1 << bitCount(x)) & 665772) != 0) {
      ++ans
    }
  }
  return ans
}
